#include <iostream>
#include "common_list.h"
#include <vector>

using namespace std;
class Solution {

public:
    ListNode *merge(ListNode* l1, ListNode *l2) {
        ListNode *temp = new ListNode;
        temp->next = nullptr;
        ListNode *ptr = temp;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                ptr->next = l1;
                l1 = l1->next;
            } else {
                ptr->next = l2;
                l2 = l2->next;
            }
            ptr = ptr->next;
        }

        if (l1)
            ptr->next = l1;
        if (l2)
            ptr->next = l2;

        return temp->next;
    }

    ListNode *split(vector<ListNode*> &vec, int l, int r) {
        int mid = l + (r-l)/2;
        if (r <= l)
            return vec[mid];
        ListNode *l1 = split(vec, l, mid);
        ListNode *l2 = split(vec, mid+1, r);
        return merge(l1, l2);
    }

    ListNode *mergeKList2(vector<ListNode*> &vec) {
        return split(vec, 0, vec.size()-1);
    }

    ListNode *mergeKList(vector<ListNode*> &vec) {
        ListNode *temp = new ListNode;
        temp->next = nullptr;
        ListNode *ptr = temp;

        if (!vec.size())
            return nullptr;

        while (1) {
            int max_idx = -1;
            for (size_t i = 0; i < vec.size(); i++) {
                if (vec[i] && max_idx == -1) {
                    max_idx = i;
                } else {
                    if (vec[i] && vec[i]->val < vec[max_idx]->val)
                        max_idx = i;
                }

            }
            if (max_idx == -1)
                break;
            else {
                ptr->next = vec[max_idx];
                ptr = ptr->next;
                vec[max_idx] = vec[max_idx]->next;
            }
        }

        return temp->next;
    }
};


int main(void)
{
    cout << "合并k个链表" << endl;

    int val1[] = {1, 4, 6};
    int val2[] = {2,  9,};
    int val3[] = {-1, 12};

    auto l10 = generate_list_val(sizeof(val1)/sizeof(int), val1);
    auto l20 = generate_list_val(sizeof(val2)/sizeof(int), val2);
    auto l30 = generate_list_val(sizeof(val3)/sizeof(int), val3);

    auto l11 = generate_list_val(sizeof(val1)/sizeof(int), val1);
    auto l21 = generate_list_val(sizeof(val2)/sizeof(int), val2);
    auto l31 = generate_list_val(sizeof(val3)/sizeof(int), val3);

    print_list(l10);
    print_list(l20);
    print_list(l30);

    cout << "普通合并法" << endl;
    vector<ListNode*> vec0 = {l10, l20, l30};
    auto new_list = Solution().mergeKList(vec0);
    print_list(new_list);

    cout << "归并法" << endl;
    vector<ListNode*> vec1 = {l11, l21, l31};
    auto new_list2 = Solution().mergeKList2(vec1);
    print_list(new_list2);


    return 0;
}